1. Technical Field
The invention relates to the conversion of data from one format to another format. More particularly, the invention relates to the conversion of interleaved data to a planar data format, for example the conversion of interleaved CMYK image data to planar image data.
2. Description of the Prior Art
Color separation is used, for example, in color printing where each of three colors (i.e. cyan, magenta, yellow) and black are printed from separate print heads. Each print head receives data from a separate portion of the printer memory, such that four copies of an image are retained in memory. That is, a separate copy of the image to be printed is retained in memory for each color, where each copy contains only the information necessary to print a particular layer of the image. This technique is referred to as CMYK or planar printing because each color layer comprises a separate plane of the resultant image.
Color separation can also be effected by generating a word of data for each pixel in the image, where such data word contains all four layers of color information for that pixel. This technique is referred to as interleaved printing because each color layer is interleaved with each other color layer to produce a word of composite color information for each pixel.
Either of the above approaches produces data that correspond to a color image and that can be stored in a memory.
Often color images are input pixel by pixel, i.e. interleaved. That is, when an image is scanned, all the information for each pixel is scanned simultaneously because the scanner physically sees one pixel first and then the next pixel in sequential order. Thus, there is a physical motivation for using the interleaved format.
On the other hand, an obvious way of storing an image for multi-pass printing is by separating the different colors over four different color planes, e.g. cyan, magenta, yellow, and black. For example, a color laser printer prints in multiple passes, where there is a printing pass for each color plane. Thus, the printer may print a first pass in cyan. It prints a next pass in magenta, and then in yellow.
Thus, it can be seen that a scanner often produces image information in an interleaved format, while a four-pass laser printer prefers such information in a planar format.
Accordingly, in such devices as color copiers, which comprise both a color scanner for capturing a color image and a color printer for recording the image on paper, there is a need for efficiently and quickly converting from an interleaved format to a planar format. It is therefore desirable to provide a technique to process the two four-color data formats, while meeting the format needs of various input and output devices, where such input and output devices use some combination of these two formats
One way of performing such conversion is to provide additional storage space, i.e. more memory, where an adequate buffer is available for each plane. Thus, the interleaved data are readily sorted in sequential order, for example in an interleaved CMYK color system, to four separate buffers, where there is one buffer for each color plane. While this approach is simple, a system having 128 MB total RAM storage capacity in which an image requires 117 MB of such storage, does not provide sufficient capacity to perform the foregoing calculation. The cost and space required to add additional memory for such calculation, e.g. an additional 117 MB of RAM, makes the implementation of such simple scheme prohibitively expensive.
It would be advantageous to provide a scheme that allows for data format conversion, e.g. between an interleaved data format and a planar data format, without significantly increasing the form factor, processor speed, or RAM memory requirements of the target device, e.g. a color copier or color laser printer.
The invention provides a technique for converting interleaved data to a planar format. The herein disclosed technique requires minimal processing power and only a small amount of additional memory. The invention comprises an algorithm that follows xe2x80x9cmap cyclesxe2x80x9d throughout a frame buffer. Such map cycles result from iterating a function that maps planar addresses to CMYK addresses as follows:
Let i=index of a planar byte in the frame buffer, then:
xe2x80x83C(i)=index of CMYK value that belongs in planar byte i
=4i, for 0 less than =i less than N,
=4(ixe2x88x92N)+1, for N less than =i less than 2N,
=4(ixe2x88x922N)+2, for 2N less than =i less than 3N,
=4(ixe2x88x923N)+3, for 3N less than =i less than 4N,
where N=the number of pixels in the frame buffer (4N=number of bytes).
The preferred method of planarizing the frame buffer is:
1. Start at an index n that has not yet been converted. Set another index i equal to the index n.
2. Save the value at i.
3. Copy the value of C(i) to i.
4. Set the index i to the next index in the cycle, which is C(i).
5. If the new index i is not the same as the index n (from 1.), then go to 3.
6. Copy the saved value (from 2.) to the most recent i (from 5) that was not equal to n.
7. The cycle starting at n is now planarized.
8. Go to 1., unless the whole file is finished. A cycle is finished when 4N copies have been made.
A key aspect of the invention involves finding the next i in step 1. Thus, C(i) is written as:
C(i)=(4i) mod Q, where Q=4Nxe2x88x921 (and its inverse is Cxe2x88x921(i)=(Ni) mod Q)
Using this form, it can be proven that:
All cycle lengths divide the 1-Cycle""s length evenly (and therefore no cycle is longer than the 1-Cycle);
If a cycle is shorter than the 1-Cycle, then its lowest index is a multiple of a factor of Q; and
If the 1-Cycle includes index i, then any j-cycle includes index (ij mod Q);
where, an i-Cycle is the cycle which contains index i, and a cycle""s length is equal to the number of distinct indices in the cycle.
Other factors taken into account include:
Indices 0 and 4Nxe2x88x921 are stationary (C(i)=i);
Indices Q/3 and 2Q/3 are stationary if 3 divides Q;
If {Q/(4n) less than =i less than =Q/((4n)xe2x88x921)}, then Cn(i)  less than =i, and i is not the lowest index in its cycle.
Because there are no quick ways to determine whether a new index i is part of a cycle that has already been converted, the formula above with regard to Cn(i) must be evaluated for every n, such that it is no different than iterating C(i) directly. Also, the structure of these cycles varies chaotically with N. A letter page sized buffer has only six cycles, each of length 10 million. If N is a pure power of four, it has the shortest possible cycles, and the greatest number of cycles. Values of N just one away from a power of four tend to have only a few cycles. Fortunately, typical page sizes tend to have few cycles.
There are three phases to the preferred algorithm according to the invention. The first two phases are order N, but the third phase takes an unpredictable amount of time. For a large value N, the third phase usually can be skipped or does not take long because the pathological N values that require significant amounts of Phase III time become increasingly spread out as N increases.
In phase I, the 1-Cycle is processed and all of its member indices that are  less than =MAX_HIT are saved in the array firstHit[] .
In phase II, all indices between 1 and MAX_HIT are visited, skipping any indices that have already been in a cycle (as recorded by the array firstHit[]). As each cycle is converted, any hits to indices between 1 and MAX_HIT are directly recorded in the array hit[], so that indices that have been used are quickly skipped when searching for future cycles.
Phase III is skipped unless there are still some copies left to process.
In phase III, there is no more space for recording every hit individually, so the rules noted above are invoked. When looking for new cycles, only indices that are not multiples of anything in the 1-Cycle are considered. Also, once the remaining number of uncycled bytes drops below the 1-Cycle""s length, all remaining cycles are known to belong to factors of Q, and the search is narrowed to those values only. When an index i is found that cannot be rejected for one of these reasons, the algorithm begins processing the cycle, but if the algorithm ever ends up at an index less than i, then this 1-Cycle has already been processed. In that case, the 1-Cycle is restored to its previous state by copying in the reverse direction, and the algorithm skips to the next candidate for i.